#include "ad_construct.h"
#include <cstdio>
#include <cstring>
#include <algorithm>

void handle_root(const char* cword, int clen, dfa * DFA, input_data & INPUT){
  char thword[MAX_WORD_LENGTH + 1];
  int i, blen = 2*clen;
  for (i=0; i<clen; i++){
    thword[i] = thword[i+clen] = cword[i];
  }
  thword[blen] = 0;
  if (blen > MAX_WORD_LENGTH){
    printf("Too small maximal length of forbidden word!\n");
    exit(1);
  }
  for (i=clen-1; i>=1; i--){
    if (DFA->bad_suffix_trie(thword + i, blen - i, 1)) return;
  }
  if (DFA->bad_suffix_trie(thword, blen - 1, 1)) return;
  DFA->add_word(thword);
  return;
}

const bool forbidden_root(const char* cword, int clen, dfa * DFA, input_data & INPUT){
  int i;
  if (clen >= 3 && DFA->bad_suffix_trie(cword + clen-3, 3, 1)) return true;
  for (i=6; i<=clen; i+=2){
    if (DFA->bad_suffix_trie(cword + clen-i, i, 1)) return true;
  }
  return false;
}

i64 construct_antidictionary(grate_config & CONFIG, input_data & INPUT, words_queue * WORDS_QUEUE, dfa * DFA){
  i64 max_words_queue_size = 0;
  
  int i, clen = 3;
  i64 marker_pos;
  char cword[MAX_WORD_LENGTH], ch;
  
  if (INPUT.ADD_X3){
    DFA->add_word("aaa");
    DFA->add_word("ababab");
  }
  else{
    WORDS_QUEUE->push_word("aaa", 2);
  }
  
  WORDS_QUEUE->push_word("aab", 2);
  WORDS_QUEUE->push_word("aba", 0);
  WORDS_QUEUE->push_word("abb", 0);

  WORDS_QUEUE->push_marker(marker_pos);
  
  while (! WORDS_QUEUE->is_empty()){
    if (WORDS_QUEUE->is_index(marker_pos)){
      if (clen < INPUT.ROOT_LENGTH){
        clen++;
        WORDS_QUEUE->push_marker(marker_pos);
        WORDS_QUEUE->pop_symbol();
        continue;
      }
      else break;
    }
    
    // there is a word in the queue starting at qbeg with (length = clen)
    for (i=0; i<clen; i++){
      cword[i] = WORDS_QUEUE->pop_symbol() + 'a';
    }
    cword[clen] = 0;
    int t1 = WORDS_QUEUE->pop_symbol();
    int t2 = WORDS_QUEUE->pop_symbol();
    int type = 2 * t1 + t2;

    if (type == 2){
      handle_root(cword, clen, DFA, INPUT);
    }
    
    if (clen < INPUT.ROOT_LENGTH){
      for (ch='a'; ch<='b'; ch++){
        cword[clen] = ch;
        cword[clen+1] = 0;
        if (forbidden_root(cword, clen+1, DFA, INPUT)) continue;
        int ctype;
        if (type >= 1) ctype = 2;
        else if (is_square(cword, clen+1)) ctype = 1;
        else ctype = 0;
        WORDS_QUEUE->push_word(cword, ctype);
      }
    }

    i64 cwqsz = WORDS_QUEUE->get_number_of_letters();
    if (cwqsz > max_words_queue_size){
      max_words_queue_size = cwqsz;
    }
  }
  delete WORDS_QUEUE;

  return max_words_queue_size;
}

const bool is_square(const char* cword, int clen){
  if (clen % 2 > 0) return false;
  int i, mid = clen / 2;
  for (i=0; i<mid; i++){
    if (cword[i] != cword[mid + i]) return false;
  }
  return true;
}
